#include<stdio.h>

void swap(int* x, int* y)
{
	int tem = *x;
	*x = *y;
	*y = tem;
}

int _quicksort(int* arr, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = prev+1;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi] && ++prev!=cur)
		{
			swap(&arr[cur], &arr[prev]);
		}
		cur++;
	}
	swap(&arr[keyi], &arr[prev]);
	return prev;
}

void quicksort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = _quicksort(arr, left, right);
	quicksort(arr, keyi + 1, right);
	quicksort(arr, left, keyi - 1);
}

int main()
{
	int arr[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
	int n = sizeof(arr) / sizeof(arr[0]);

	quicksort(arr, 0, n - 1);

	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	return 0;
}